package com.zlk.algorithm.algorithm.dynamicPlan.PartitionedKnapsack074;

import org.junit.Test;

// 通配符匹配（和题目4高度相似，只是边界条件不同而已，而且更简单）
// 给你字符串s、字符串p
// s中一定不含有'?'、'*'字符，p中可能含有'?'、'*'字符
// '?' 表示可以变成任意字符，数量1个
// '*' 表示可以匹配任何字符串（包括空字符序列）。
// 请实现一个支持 '?' 和 '*' 的通配符匹配
// 返回p的整个字符串能不能匹配出s的整个字符串
// 测试链接 : https://leetcode.cn/problems/wildcard-matching/
public class Code05_WildcardMatching {


    @Test
    public void test(){
        System.out.println(isMatch("", "******"));
    }

    /**
     * 可能性分析
     * s,p   位置分别为i和j
     * 1、 j不等于特殊字符
     *    s[i]==p[j]  找f(i+1,j+1)
     *    s[i]!=p[j]  return false;
     *
     * 2、 j等于？
     *    直接找f(i+1,j+1)
     *
     * 3、j等于*
     *     1 2 3 4 5 6 78 78
     *     1 2   *  78
     *
     *     循环 i+1 到 s.len
     *     f(k,j+1)
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
//        int[][] dp = new int[s.length()+1][p.length()+1];
//        return f(s.toCharArray(),p.toCharArray(),0,0,dp);
        return f(s.toCharArray(),p.toCharArray());
    }

    //严格位置依赖的动态规划
    private boolean f(char[] s, char[] p) {
        int n = s.length;
        int m = p.length;
        boolean[][] dp = new boolean[n+1][m+1];
        dp[n][m] = true;
        for (int j = m-1; j >=0; j--) {
            dp[n][j]=p[j]=='*'&&dp[n][j+1];
        }
        for (int i = n-1; i >=0; i--) {
            for (int j = m-1; j >=0 ; j--) {
                if (p[j] != '*') {
                    dp[i][j] = (s[i] == p[j] || p[j] == '?') && dp[i+1][j+1];
                }else{
                    dp[i][j] = dp[i+1][j]||dp[i][j+1];
                }
            }
        }
        return dp[0][0];
    }


    private boolean f(char[] s, char[] p, int i, int j,int[][] dp) {
        //base case
        if(dp[i][j]!=0){
            return dp[i][j]==1;
        }
        boolean ans;
        if(i==s.length){
            if(j==p.length){
                ans= true;
            }else{
                if(p[j]!='*'){
                    return false;
                }else{
                    boolean f = f(s, p, i, j + 1, dp);
                    ans= f;
                }
            }
        }else if(j==p.length){
            ans= false;
        }else{
            char si = s[i];
            char pj = p[j];
            if(pj=='*'){
                // j为空串情况
//            boolean temp = f(s,p,i,j+1);
//            int k = i+1;
//            while (k<=s.length){
//                temp|=f(s,p,k++,j+1);
//            }
//            return temp;
                //1、处理当前i位置
                boolean b1 = f(s,p,i+1,j,dp);
                boolean b2 = f(s,p,i,j+1,dp);
                ans = b1||b2;
                // dp优化
            }else{
                ans =(si==pj||pj=='?')&&f(s,p,i+1,j+1,dp);
            }
        }
        dp[i][j]= ans?1:2;
        return ans;
    }


    private boolean f(char[] s, char[] p, int i, int j) {
        //base case
        if(i==s.length){
            if(j==p.length){
                return true;
            }else{
                if(p[j]!='*'){
                    return false;
                }else{
                    return f(s,p,i,j+1);
                }
            }
        }else{
            if(j==p.length){
                return false;
            }
        }
        char si = s[i];
        char pj = p[j];
        if(pj=='*'){
            // j为空串情况
//            boolean temp = f(s,p,i,j+1);
//            int k = i+1;
//            while (k<=s.length){
//                temp|=f(s,p,k++,j+1);
//            }
//            return temp;
            //1、处理当前i位置
            boolean b1 = f(s,p,i+1,j);
            boolean b2 = f(s,p,i,j+1);
            return b1||b2;
            // dp优化
        }else{
            return (si==pj||pj=='?')&&f(s,p,i+1,j+1);
        }
    }

}
